import sortedcontainers


class Solution(object):
    def averageHeightOfBuildings(self, buildings):
        h_d = sortedcontainers.SortedDict()
        num_d = sortedcontainers.SortedDict()
        for u, v, h in buildings:
            h_d[u] = h_d.setdefault(u, 0) + h
            num_d[u] = num_d.setdefault(u, 0) + 1
            h_d[v] = h_d.setdefault(v, 0) - h
            num_d[v] = num_d.setdefault(v, 0) - 1
        n = len(h_d)
        st = []
        key = list(h_d.keys())
        for i in range(1, n):
            h_d[key[i]] += h_d[key[i - 1]]
            num_d[key[i]] += num_d[key[i - 1]]
        for i in range(n - 1):
            u, h = h_d.peekitem(i)
            u, num = num_d.peekitem(i)
            v, _ = h_d.peekitem(i + 1)
            if num > 0:
                if st and st[-1][2] == h // num and st[-1][1] == u:
                    last_u, last_v, last_h = st.pop()
                    node = [last_u, v, last_h]
                else:
                    node = [u, v, h // num]
                st.append(node)
        return st


data = Solution()
buildings = [[1, 4, 2], [3, 9, 3]]
print(data.averageHeightOfBuildings(buildings))
